The graphical quality of computer games has improved from blocky computer-generated images to more life-like three-dimensional images. Three-dimensional objects are usually represented by groups of connected triangles which collectively appear to form a surface of a virtual object. Among other things, each triangle in a virtual object is defined by three vertices and three normals. As is known in the art, each vertex of a triangle used to model a three-dimensional surface is specified by an X, Y and a Z coordinate.
As computer graphic applications (programs) require more detailed and more realistic three-dimensional images, the number of triangles required to represent each scene increases. As the number of triangles increases, the limit to graphics processing capability frequently becomes a bandwidth limitation of the data bus that connects the CPU (the central processor unit of a computer system on which the graphic application is running) to the Graphics Processing Unit (GPU).
FIG. 1 depicts a computer system having a CPU 2 such as a microprocessor or microcontroller. The CPU 2 executes instructions stored in RAM and/or ROM 3 and it is coupled to a GPU 4 over a system bus 5. The GPU 4 provides graphics processing capability to the CPU 2 and the GPU 4 output is provided to a display 6, typically a CRT or LCD display device (not shown for clarity).
An alternate approach to overcome bus bandwidth limitations yet provide more realistic graphics is to use some form of a higher-order surface to represent three-dimensional objects, rather than planar triangles. A higher-order surface defines a three-dimensional, curved, surface with a compact representation. One such higher-order surface is known as Point Normal Triangles or PN Triangles. Current GPU art does not provide native support for the processing and display of higher-order surfaces. A process known as tessellation can be performed on higher-order surfaces to decompose the higher-order surfaces into a mesh of planar, triangular surfaces, said surfaces approximating the actual higher-order surface. In order for this tessellation process to be of benefit in reducing the bandwidth constraint described earlier, it must be provided by and therefore “exist” on the GPU. In such a system, the CPU will transfer higher-order surface data to the GPU over the CPU to GPU data bus. The GPU will then tessellate the higher-order surfaces into triangles that approximate the surfaces. The triangles then become input to standard GPU resources that cause the approximated higher-order surfaces to be displayed.
The amount or degree to which a triangle is tessellated into smaller triangles is known as a tessellation level. Discrete tessellation requires that all triangles be divided (tessellated) into a fixed number of similar triangles (equally spaced in barycentric coordinate space). The higher the tessellation level, the more tessellated triangles generated and the more accurate the surface approximation, however, higher tessellation comes at the expense of processing resources. The discrete nature of the tessellation means that switching tessellation levels for a given surface from one display frame to the next will result in a significant change in the object's appearance—a change that is likely to be visually unacceptable.
Continuous tessellation provides for smoothly varying amounts of tessellation between discrete tessellation levels. In general, the triangles resulting from continuous tessellation are not similar, and are not equally spaced in barycentric coordinate space.
Curves in space can be represented by a Bezier curve, which provides a mathematical model of a curve. As is known, a Bezier curve has first and second end points and control points; it is the control points that define curvature proximate to the control points. A cubic Bezier curve has four control points: one for each end point and two control points inside the curve. The concept of the Bezier curve can be extended to construct a Bezier surface in which surface curvature is described using control points. A problem with tessellating triangles in order to provide more life-like surface modeling is the computational power required to evaluate a Bezier function, or other curved-surface model. A method and apparatus by which a higher-order surface can be efficiently tessellated so as to more quickly model a graphical surface would be an improvement over the prior art.